#include "Iterator.h"
using namespace std;

// 自定义双向链表节点
template<typename T>
struct Node {
    T data;
    Node* prev;
    Node* next;
    
    explicit Node(const T& value) : data(value), prev(nullptr), next(nullptr) {}
};

// 自定义双向链表迭代器
template<typename T>
class ListIterator : public iterator<
    bidirectional_iterator_tag,
    T,
    ptrdiff_t,
    T*,
    T&
> {
private:
    Node<T>* current;

public:
    // 构造函数
    explicit ListIterator(Node<T>* node = nullptr) : current(node) {}
    
    // 解引用操作符
    T& operator*() const {
        if (!current) throw std::runtime_error("Dereferencing null iterator");
        return current->data;
    }
    
    T* operator->() const {
        if (!current) throw std::runtime_error("Dereferencing null iterator");
        return &(current->data);
    }
    
    // 递增操作符
    ListIterator& operator++() {
        if (!current) throw std::runtime_error("Incrementing null iterator");
        current = current->next;
        return *this;
    }
    
    ListIterator operator++(int) {
        ListIterator temp = *this;
        ++(*this);
        return temp;
    }
    
    // 递减操作符
    ListIterator& operator--() {
        if (!current) throw std::runtime_error("Decrementing null iterator");
        current = current->prev;
        return *this;
    }
    
    ListIterator operator--(int) {
        ListIterator temp = *this;
        --(*this);
        return temp;
    }
    
    // 比较操作符
    bool operator==(const ListIterator& other) const {
        return current == other.current;
    }
    
    bool operator!=(const ListIterator& other) const {
        return !(*this == other);
    }
    
    // 获取底层节点
    Node<T>* getNode() const { return current; }
};

// 自定义双向链表
template<typename T, typename Allocator = std::allocator<T>>
class LinkedList {
private:
    using AllocTraits = std::allocator_traits<Allocator>;
    using NodeAllocator = typename AllocTraits::template rebind_alloc<Node<T>>;
    using NodeTraits = std::allocator_traits<NodeAllocator>;
    
    Node<T>* head;
    Node<T>* tail;
    size_t count;
    NodeAllocator alloc;

public:
    // 类型定义
    using value_type = T;
    using reference = T&;
    using const_reference = const T&;
    using iterator = ListIterator<T>;
    using const_iterator = ListIterator<const T>;
    using size_type = size_t;
    
    // 构造函数
    LinkedList() : head(nullptr), tail(nullptr), count(0) {}
    
    // 析构函数
    ~LinkedList() {
        clear();
    }
    
    // 添加元素到尾部
    void push_back(const T& value) {
        Node<T>* newNode = NodeTraits::allocate(alloc, 1);
        NodeTraits::construct(alloc, newNode, value);
        
        if (!tail) {
            head = tail = newNode;
        } else {
            newNode->prev = tail;
            tail->next = newNode;
            tail = newNode;
        }
        ++count;
    }
    
    // 删除元素
    void pop_back() {
        if (!tail) return;
        
        Node<T>* oldTail = tail;
        tail = tail->prev;
        
        if (tail) {
            tail->next = nullptr;
        } else {
            head = nullptr;
        }
        
        NodeTraits::destroy(alloc, oldTail);
        NodeTraits::deallocate(alloc, oldTail, 1);
        --count;
    }
    
    // 清空链表
    void clear() {
        while (head) {
            Node<T>* next = head->next;
            NodeTraits::destroy(alloc, head);
            NodeTraits::deallocate(alloc, head, 1);
            head = next;
        }
        head = tail = nullptr;
        count = 0;
    }
    
    // 获取大小
    size_type size() const { return count; }
    
    // 迭代器接口
    iterator begin() { return iterator(head); }
    iterator end() { return iterator(nullptr); }
    
    const_iterator begin() const { return const_iterator(const_cast<Node<T>*>(head)); }
    const_iterator end() const { return const_iterator(nullptr); }
    
    const_iterator cbegin() const { return const_iterator(const_cast<Node<T>*>(head)); }
    const_iterator cend() const { return const_iterator(nullptr); }
};

// 使用示例
int main() {
    LinkedList<int> list;
    
    // 添加元素
    list.push_back(10);
    list.push_back(20);
    list.push_back(30);
    
    // 使用迭代器遍历
    std::cout << "List contents: ";
    for (auto it = list.begin(); it != list.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    
    // 使用范围for循环
    std::cout << "Range-based for loop: ";
    for (const auto& value : list) {
        std::cout << value << " ";
    }
    std::cout << std::endl;
    
    // 使用STL算法
    std::cout << "Reverse order: ";
    std::for_each(
        std::reverse_iterator<LinkedList<int>::iterator>(list.end()),
        std::reverse_iterator<LinkedList<int>::iterator>(list.begin()),
        [](int value) { std::cout << value << " "; }
    );
    std::cout << std::endl;
    
    return 0;
}  